Algorithme CORDIC

L’algorithme CORDIC (Coordinate Rotation Digital Computing) est un algorithme inventé en 1959 et utilisé dans les calculatrices. Cet algorithme est adapté pour calculer les valeurs des fonctions trigonométriques. Pour celui-ci, certaines valeurs particulières du logarithme sont stockées dans la mémoire de la machine : il s’agit des valeurs approchés de \(\ln(10)\) , \(\ln(2)\) , \(\ln(1,1)\) , \(\ln(1,01)\) , \(\ln(1,001)\) , \(\ln(1,0001)\) … 
Ces dernières sont toutes de la forme \(\ln(1+10^{−k})\) , où  \(k\) est un entier naturel.

On prend un réel \(x\)  entre 1 et 10.

• Puisque la suite  \((2^n)\) tend vers \(+\infty\) , il existe un entier  \(n_0\) tel que   \(x\times 2^{n_0} \leqslant 10 \leqslant x \times 2^{n_0+1}\) . Il s'avère que cet entier vaut au maximum 3, mais ce n'est pas important...
  
• Puisque la suite \((1,1^n)\)  tend vers \(+\infty\) , il existe un entier \(n_1\)  tel que \(x \times 2^{n_0} \times 1,1^{n_1} \leqslant 10 \leqslant x \times 2^{n_0} \times 1,1^{n_1+1}\) .
• Puisque la suite \((1,01^n)\)  tend vers \(+\infty\) , il existe un entier \(n_2\)  tel que \(x \times 2^{n_0} \times 1,1^{n_1} \times 1,01^{n_2} \leqslant 10 \leqslant x \times 2^{n_0} \times 1,1^{n_1} \times 1,01^{n_2+1}\) ...

Et ainsi de suite : on établit un \(k\) -uplet d'entiers naturels \((n_0, n_1, n_2, \dots, n_k)\)  et on approche  \(x\) par la valeur \(x\simeq\dfrac{10}{2^{n_0} \times 1,1^{n_1} \times 1,01^{n_2} \times \dots \times (1+10^{-k})^{n_k}}\) .

Il s'agit en fait d'appliquer plusieurs fois de suite un algorithme de seuil.
Il en vient que 
\(\ln(x) \simeq \ln(10) - n_0 \ln(2)-n_1\ln(1,1)-n_2\ln(1,01)- \dots - n_k \ln(1+10^{-k})\) .

Cet algorithme est très efficace puisque la multiplication par `1+10^{-k}` est rapide. L'algorithme CORDIC peut alors être implémenté de la façon suivante.

from math import log
# En Python, le logarithme népérien s'écrit log

def cordic(x , n = 10) :
    '''
    x : un réel entre 1 et 10 dont on veut calculer le logarithme népérien
    n : la plus grande valeur de k pour laquelle ln(1+10^(-k)) est stockée en mémoire
    '''
    log_x = log(10)
    for k in range(n+1) :
        z = 1 + 10 ** (-k)
        while x * z <= 10 :
            x = x * z
            log_x = log_x - log(z) #log(z) est en mémoire, on peut l'utiliser ici
    return log_x

Exercice

L'algorithme ci-dessus, implémenté en Python, permet de calculer une valeur approchée du logarithme d'un réel  \(x\) entre 1 et 10.

Expliquer à quoi servent les instructions des trois dernières lignes.